import java.util.*;
import java.lang.*;
import java.util.regex.*;
import java.io.*;
import java.awt.*;
import java.io.RandomAccessFile;
import java.nio.*;
import java.nio.channels.*;
/*

public class GeoFence {
	
	ArrayList<Point> pointList;
	ArrayList<Polygon> polyList;
	// Record the ts table of polygon for each id.
	Hashtable<Integer,ArrayList<Integer>> polyTsTable;
	ArrayList<ResultClass> resultList;
	String inPointFile = "";
	String inPolyFile = "";
	String outFile = "";
	public long polyTime;
	boolean ifInside;
	int withinDist;
	
	public GeoFence(String inPointFile,String inPolyFile,String outFile){
		this.inPointFile = inPointFile;
		this.inPolyFile = inPolyFile;
		this.outFile = outFile;
		polyTsTable = new Hashtable();
		
		System.out.println("Start");
		polyTime = System.currentTimeMillis();
		readPoint();
		readPoly();
		long stopTime = System.currentTimeMillis();
	    long elapsedTime = stopTime - polyTime;
	    System.out.println("Read:"+elapsedTime);
	    
		polyTime = System.currentTimeMillis();
		checkInside(8);
		withinDist = 1000;
		//checkWithin();
		stopTime = System.currentTimeMillis();
	     elapsedTime = stopTime - polyTime;
	      System.out.println("CheckInside:"+elapsedTime);
		//printResult();
	      outputResult();
		
	}
	
	private void readPoint(){
		BufferedReader br = null;
		pointList = new ArrayList();
		String pattern = "POINT:([0-9]*):([0-9]*).*<gml:Point srsName=\"EPSG:54004\" xmlns:gml=\"http://www.opengis.net/gml\"><gml:coordinates decimal=\".\" cs=\",\" ts=\" \">(.*) </gml:coordinates></gml:Point>";
		Pattern r = Pattern.compile(pattern);
		try {
 
			String sCurrentLine;
 
			br = new BufferedReader(new FileReader(inPointFile));
 
		    while ((sCurrentLine = br.readLine()) != null) {
		    	Matcher m1 = r.matcher(sCurrentLine);
		    	if(m1.find()){
					
				   //System.out.println( m1.group(0));
				   int id = Integer.parseInt(m1.group(1));
				   int ts = Integer.parseInt(m1.group(2));
				   String[] s = m1.group(3).split(",");
				   //System.out.println(s[0]+" "+s[1]);
				   pointList.add(new Point(id,ts,Double.parseDouble(s[0]),Double.parseDouble(s[1])));
		   
			 }
				
			}
 
		 } catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				if (br != null)br.close();
			} catch (IOException ex) {
				ex.printStackTrace();
			}
		}
	}
	
	private void readPoly(){
		BufferedReader br = null;
		polyList = new ArrayList();
		String pattern = "POLYGON:([0-9]*):([0-9]*).*<gml:outerBoundaryIs><gml:LinearRing><gml:coordinates decimal=\".\" cs=\",\" ts=\" \">(.*)</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs>";
		String pattern2 = "<gml:innerBoundaryIs><gml:LinearRing><gml:coordinates decimal=\".\" cs=\",\" ts=\" \">(.*)</gml:coordinates></gml:LinearRing></gml:innerBoundaryIs>";
		
		Pattern r = Pattern.compile(pattern);
		Pattern r2 = Pattern.compile(pattern2);
		try {
 
			String sCurrentLine;
 
			br = new BufferedReader(new FileReader(inPolyFile));
 
		    while ((sCurrentLine = br.readLine()) != null) {
		    	Matcher m1 = r.matcher(sCurrentLine);
		    	Matcher m2 = r2.matcher(sCurrentLine);
		    	if(m1.find()){
					
				   //System.out.println( m1.group(0));
				   int id = Integer.parseInt(m1.group(1));
				   int ts = Integer.parseInt(m1.group(2));
				   String[] s = m1.group(3).split(" ");
				   ArrayList<Point> polyPoint = new ArrayList();
				   for(String substr:s){
					   String[] pstr = substr.split(",");
					// if(id==12 && ts==12) System.out.println(pstr[0]+" "+pstr[1]);
					   polyPoint.add(new Point(Double.parseDouble(pstr[0]),Double.parseDouble(pstr[1])));
				   }
				   Point[] outArray = polyPoint.toArray(new Point[polyPoint.size()]); 
				 		 
			   if( m2.find()) {
				   s = m2.group(1).split(" ");
				   ArrayList<Point> polyPoint2 = new ArrayList();
				   for(String substr:s){
					   String[] pstr = substr.split(",");
					  // System.out.println(pstr[0]+" "+pstr[1]);
					   polyPoint2.add(new Point(Double.parseDouble(pstr[0]),Double.parseDouble(pstr[1])));
				   }
				   Point[] inArray = polyPoint2.toArray(new Point[polyPoint2.size()]);
				   
				   if(outArray==null) System.out.println("out");
				   if(inArray==null) System.out.println("in");
				   polyList.add(new Polygon(id,ts,inArray,outArray));
				  				   
			   }
			   else{
				    polyList.add( new Polygon(id,ts,outArray));
					
			   }
			   // Update polygon ts hashtable
			   if(polyTsTable.containsKey(id))
			   {
				   ArrayList tempList =  polyTsTable.get(id);
				   tempList.add(ts);
				   polyTsTable.put(id, tempList ); 
			   }
			   else{
				   ArrayList<Integer> tempList = new ArrayList();
				   tempList.add(ts);
				   polyTsTable.put(id, tempList ); 
			   }
			   
			 }
				
			}
 
		 } catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				if (br != null)br.close();
			} catch (IOException ex) {
				ex.printStackTrace();
			}
		}
	}
	
	private int checkSequence(int pointTs , int polyId){
		ArrayList myList = polyTsTable.get(polyId);
		int maxPolyTs = (Integer)myList.get(0);
		for(int i = 1 ; i<myList.size();i++){
			int currTs;
			if((currTs=(Integer)myList.get(i))<pointTs && currTs>maxPolyTs) maxPolyTs = currTs; 
		}
		return maxPolyTs;
	}
	
	private void checkInside(){
		resultList  = new ArrayList();
		int i=0;
		while(i<pointList.size()){
			Point tempPoint = pointList.get(i);
			int j = 0;
			while( j < polyList.size()){
				Polygon tempPoly = polyList.get(j);
				if(tempPoly.timestamp == checkSequence(tempPoint.timestamp , tempPoly.getid())){
					if(GeoTool.ifInPolygon(tempPoint, tempPoly)){
						//System.out.println(tempPoint.id+":"+tempPoint.timestamp+":"+tempPoly.getid()+":"+tempPoly.gettimestamp());
						resultList.add(new ResultClass(tempPoint.id,tempPoint.timestamp,tempPoly.getid(),tempPoly.gettimestamp()));
					}
				}
				j++;
			}
			i++;
		}
	}
	
	private void checkInside(int nThreads){
		resultList  = new ArrayList();
		Thread[] mythread = new InsideThread[nThreads];
		for(int i = 0; i<nThreads;i++){
			mythread[i] = new InsideThread(i,nThreads);
			mythread[i].start();
		}
		try{
			for(Thread m : mythread){
				m.join();
			}
		}catch(Exception e){
			
		}
		
	}
	
	private void checkWithin(int nThreads){
		resultList  = new ArrayList();
		Thread[] mythread = new InsideThread[nThreads];
		for(int i = 0; i<nThreads;i++){
			mythread[i] = new InsideThread(i,nThreads);
			mythread[i].start();
		}
		try{
			for(Thread m : mythread){
				m.join();
			}
		}catch(Exception e){
			
		}
	}
	
	private void checkWithin(){
		resultList  = new ArrayList();
		int i=0;
		while(i<pointList.size()){
			Point tempPoint = pointList.get(i);
			int j = 0;
			while( j < polyList.size()){
				Polygon tempPoly = polyList.get(j);
				if(tempPoly.timestamp == checkSequence(tempPoint.timestamp , tempPoly.getid())){
					if(GeoTool.ifWithinPolygon(tempPoint, tempPoly, withinDist )){
						//System.out.println(tempPoint.id+":"+tempPoint.timestamp+":"+tempPoly.getid()+":"+tempPoly.gettimestamp());
						resultList.add(new ResultClass(tempPoint.id,tempPoint.timestamp,tempPoly.getid(),tempPoly.gettimestamp()));
					}
				}
				j++;
			}
			i++;
		}
	}
	
	class InsideThread extends Thread {
		  private int index;
		  private int n;
		  InsideThread(int index,int n) {
		    this.index = index;
		    this.n = n;
		  }

		  @Override
		  public void run() {
			  if( index < n-1){
				  for(int i = (index*pointList.size())/n ; i<((index+1)*pointList.size())/n-1;i++){
						Point tempPoint = pointList.get(i);
						int j = 0;
						while( j < polyList.size()){
							Polygon tempPoly = polyList.get(j);
							if(tempPoly.timestamp == checkSequence(tempPoint.timestamp , tempPoly.getid())){
								if(GeoTool.ifInPolygon(tempPoint, tempPoly)){
									//System.out.println(tempPoint.id+":"+tempPoint.timestamp+":"+tempPoly.getid()+":"+tempPoly.gettimestamp());
									synchronized (resultList) {
								          // mutual exclusive section
										resultList.add(new ResultClass(tempPoint.id,tempPoint.timestamp,tempPoly.getid(),tempPoly.gettimestamp()));
								     }
								}
							}
							j++;
						}
						
					}
			  }
			  else{
				  for(int i = (index*pointList.size())/n ; i<pointList.size();i++){
						Point tempPoint = pointList.get(i);
						int j = 0;
						while( j < polyList.size()){
							Polygon tempPoly = polyList.get(j);
							if(tempPoly.timestamp == checkSequence(tempPoint.timestamp , tempPoly.getid())){
								if(GeoTool.ifInPolygon(tempPoint, tempPoly)){
									//System.out.println(tempPoint.id+":"+tempPoint.timestamp+":"+tempPoly.getid()+":"+tempPoly.gettimestamp());
									synchronized (resultList) {
										resultList.add(new ResultClass(tempPoint.id,tempPoint.timestamp,tempPoly.getid(),tempPoly.gettimestamp()));
									}
								}
							}
							j++;
						}						
					}
			  }
		  }
		} 
	class WithinThread extends Thread {
		  private int index;
		  private int n;
		  WithinThread(int index,int n) {
		    this.index = index;
		    this.n = n;
		  }

		  @Override
		  public void run() {
			  if( index < n-1){
				  for(int i = (index*pointList.size())/n ; i<((index+1)*pointList.size())/n-1;i++){
						Point tempPoint = pointList.get(i);
						int j = 0;
						while( j < polyList.size()){
							Polygon tempPoly = polyList.get(j);
							if(tempPoly.timestamp == checkSequence(tempPoint.timestamp , tempPoly.getid())){
								if(GeoTool.ifWithinPolygon(tempPoint, tempPoly, withinDist )){
									//System.out.println(tempPoint.id+":"+tempPoint.timestamp+":"+tempPoly.getid()+":"+tempPoly.gettimestamp());
									synchronized (resultList) {
										resultList.add(new ResultClass(tempPoint.id,tempPoint.timestamp,tempPoly.getid(),tempPoly.gettimestamp()));
									}
								}
							}
							j++;
						}
						
					}
			  }
			  else{
				  for(int i = (index*pointList.size())/n ; i<pointList.size();i++){
						Point tempPoint = pointList.get(i);
						int j = 0;
						while( j < polyList.size()){
							Polygon tempPoly = polyList.get(j);
							if(tempPoly.timestamp == checkSequence(tempPoint.timestamp , tempPoly.getid())){
								if(GeoTool.ifWithinPolygon(tempPoint, tempPoly, withinDist )){
									//System.out.println(tempPoint.id+":"+tempPoint.timestamp+":"+tempPoly.getid()+":"+tempPoly.gettimestamp());
									synchronized (resultList) {
										resultList.add(new ResultClass(tempPoint.id,tempPoint.timestamp,tempPoly.getid(),tempPoly.gettimestamp()));
									}
								}
							}
							j++;
						}						
					}
			  }
		  }
		} 
	
	private void printResult(){
		Collections.sort(resultList);
		int i=0;
		while(i<resultList.size()){
			System.out.println(resultList.get(i).getResult());
			i++;
		}
	}
	
	private String padRight(String s, int n) {
	     return String.format("%1$-" + n + "s", s);  
	}
	
	private void outputResult(){
		Collections.sort(resultList);
		int i=0;
		try { 
			File file = new File(outFile);
 
			// if file doesnt exists, then create it
			if (!file.exists()) {
				file.createNewFile();
			}
 
			FileWriter fw = new FileWriter(file.getAbsoluteFile());
			BufferedWriter bw = new BufferedWriter(fw);
			while(i<resultList.size()){
				bw.write(padRight(resultList.get(i).getResult(),80)+"\n");
				i++;
			}
			
			bw.close();
 
			//System.out.println("Done");
 
		} catch (IOException e) {
			e.printStackTrace();
		}
		
		
	}
	
	public static void main(String[] args){
	
		long startTime = System.currentTimeMillis();
		new GeoFence("./TrainingDataSet/points1000.txt","./TrainingDataSet/poly15.txt","./Result/r3.txt");		
		  long stopTime = System.currentTimeMillis();
	      long elapsedTime = stopTime - startTime;
	      System.out.println("Total:"+elapsedTime);
	      Runtime runtime = Runtime.getRuntime();
	      // Run the garbage collector
	      runtime.gc();
	      // Calculate the used memory
	      long memory = runtime.totalMemory() - runtime.freeMemory();
	      System.out.println("Used memory is: " + memory/1024 + " MB");
	}
}
*/

public class GeoFence {
	
	ArrayList<Point> pointList;
	ArrayList<ModifyPolygon> polyList;
	// Record the ts table of polygon for each id.
	Hashtable<Integer,ArrayList<Integer>> polyTsTable;
	ArrayList<ResultClass> resultList;
	String inPointFile = "";
	String inPolyFile = "";
	String outFile = "";
	public long polyTime;
	boolean ifInside;
	int withinDist;
	long outputSize;
	
	public GeoFence(String inPointFile,String inPolyFile,String outFile){
		this.inPointFile = inPointFile;
		this.inPolyFile = inPolyFile;
		this.outFile = outFile;
		polyTsTable = new Hashtable();
		
		System.out.println("Start");
		polyTime = System.currentTimeMillis();
		readInput();
		long stopTime = System.currentTimeMillis();
	    long elapsedTime = stopTime - polyTime;
	    System.out.println("Read:"+elapsedTime);
	    
		polyTime = System.currentTimeMillis();
		int cores = Runtime.getRuntime().availableProcessors();
		checkInside(cores);
		//withinDist = 1000;
	//	checkWithin(8);
		stopTime = System.currentTimeMillis();
	     elapsedTime = stopTime - polyTime;
	      System.out.println("CheckInside:"+elapsedTime);
		//printResult();
	      polyTime = System.currentTimeMillis();
	      outputResult();
	      stopTime = System.currentTimeMillis();
		  elapsedTime = stopTime - polyTime;
		  System.out.println("PrintResult:"+elapsedTime);
		
	}
	
	public GeoFence(String inPointFile,String inPolyFile,String outFile,int dist){
		this.inPointFile = inPointFile;
		this.inPolyFile = inPolyFile;
		this.outFile = outFile;
		polyTsTable = new Hashtable();
		
		System.out.println("Start");
		polyTime = System.currentTimeMillis();
		readInput();
		long stopTime = System.currentTimeMillis();
	    long elapsedTime = stopTime - polyTime;
	    System.out.println("Read:"+elapsedTime);
	    
		polyTime = System.currentTimeMillis();
	//	checkInside(8);
		withinDist = dist;
		int cores = Runtime.getRuntime().availableProcessors();
		checkWithin(cores);
		stopTime = System.currentTimeMillis();
	     elapsedTime = stopTime - polyTime;
	      System.out.println("CheckInside:"+elapsedTime);
		//printResult();
	      polyTime = System.currentTimeMillis();
	      outputResult();
	      stopTime = System.currentTimeMillis();
		  elapsedTime = stopTime - polyTime;
		  System.out.println("PrintResult:"+elapsedTime);
		
	}
	
	private void readInput(){
		Thread pointThread = new readPointThread();		
		Thread polyThread = new readPolyThread();
		pointThread.start();
		polyThread.start();
		try{
			polyThread.join();
			pointThread.join();
		}catch(Exception e){
		}
	}
	
	private void readInputNIO(){
		Thread pointThread = new readPointNIOThread();		
		Thread polyThread = new readPolyNIOThread();
		pointThread.start();
		polyThread.start();
		try{
			polyThread.join();
			pointThread.join();
		}catch(Exception e){
		}
	}
	
	class readPointThread extends Thread {
		  @Override
		  public void run() {
			  readPoint();
		  }
	}
	
	class readPointNIOThread extends Thread {
		  @Override
		  public void run() {
			  readPointNIO();
		  }
	}
	
	class readPolyThread extends Thread {
		  @Override
		  public void run() {
			  readPoly();
		  }
	}
	
	class readPolyNIOThread extends Thread {
		  @Override
		  public void run() {
			  readPolyNIO();
		  }
	}
	
	private void readPoint(){
		BufferedReader br = null;
		pointList = new ArrayList();
		String pattern = "POINT:([0-9]*):([0-9]*).*<gml:Point srsName=\"EPSG:54004\" xmlns:gml=\"http://www.opengis.net/gml\"><gml:coordinates decimal=\".\" cs=\",\" ts=\" \">(.*) </gml:coordinates></gml:Point>";
		Pattern r = Pattern.compile(pattern);
		try {
 
			String sCurrentLine;
 
			br = new BufferedReader(new FileReader(inPointFile));
 
		    while ((sCurrentLine = br.readLine()) != null) {
		    	Matcher m1 = r.matcher(sCurrentLine);
		    	if(m1.find()){
					
				   //System.out.println( m1.group(0));
				   int id = Integer.parseInt(m1.group(1));
				   int ts = Integer.parseInt(m1.group(2));
				   //String[] s = m1.group(3).split(",");
				   //System.out.println(s[0]+" "+s[1]);
				 //pointList.add(new Point(id,ts,Double.parseDouble(s[0]),Double.parseDouble(s[1])));
				   
				   StringTokenizer st = new StringTokenizer(m1.group(3),",");				
				   pointList.add(new Point(id,ts,Double.parseDouble(st.nextToken()),Double.parseDouble((String)st.nextToken())));
				   
		    	}
				
			}
 
		 } catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				if (br != null)br.close();
			} catch (IOException ex) {
				ex.printStackTrace();
			}
		}
	}
	
	private void readPointNIO(){
		//BufferedReader br = null;
		pointList = new ArrayList();
		String pattern = "POINT:([0-9]*):([0-9]*).*<gml:Point srsName=\"EPSG:54004\" xmlns:gml=\"http://www.opengis.net/gml\"><gml:coordinates decimal=\".\" cs=\",\" ts=\" \">(.*) </gml:coordinates></gml:Point>";
		Pattern r = Pattern.compile(pattern);
		String sCurrentLine;
		
		try {
			 
			RandomAccessFile f = new RandomAccessFile(inPointFile, "r");
			MappedByteBuffer in = f.getChannel().map(FileChannel.MapMode.READ_ONLY, 0, f.length());
			//System.out.println(f.length());
			int size=0;
			long len = f.length();
			//Vector<Character> b = new Vector<Character>(); 
		//	ArrayList<Character> b = new ArrayList<Character>();
			StringBuilder sb = new StringBuilder();
			
		    while (size<len) 
		    {
		    	
		    	char newChar = (char)in.get(size);
		    	if(newChar != '\n'){
		    		sb.append(newChar);
		    		//System.out.print(newChar);
		    		
		    	}
		    	else{
		    		//
		    		
		    		sCurrentLine=sb.toString();		
		

			    	Matcher m1 = r.matcher(sCurrentLine);
			    	if(m1.find()){
						
					   //System.out.println( m1.group(0));
					   int id = Integer.parseInt(m1.group(1));
					   int ts = Integer.parseInt(m1.group(2));
					  // String[] s = m1.group(3).split(",");
					   StringTokenizer st = new StringTokenizer(m1.group(3),",");	
					   //System.out.println(s[0]+" "+s[1]);
					   pointList.add(new Point(id,ts,Double.parseDouble(st.nextToken()),Double.parseDouble(st.nextToken())));
			   
			    	}
			    	sb = new StringBuilder();
		    	}
		    	size++;
				
			}
 
		 } catch (Exception e) {
			e.printStackTrace();
		} 
	}
	
	private void readPoly(){
		BufferedReader br = null;
		polyList = new ArrayList();
		String pattern = "POLYGON:([0-9]*):([0-9]*).*<gml:outerBoundaryIs><gml:LinearRing><gml:coordinates decimal=\".\" cs=\",\" ts=\" \">(.*)</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs>";
		String pattern2 = "<gml:innerBoundaryIs><gml:LinearRing><gml:coordinates decimal=\".\" cs=\",\" ts=\" \">(.*)</gml:coordinates></gml:LinearRing></gml:innerBoundaryIs>";
		
		Pattern r = Pattern.compile(pattern);
		Pattern r2 = Pattern.compile(pattern2);
		try 
		{
 
			String sCurrentLine;
 
			br = new BufferedReader(new FileReader(inPolyFile));
 
		    while ((sCurrentLine = br.readLine()) != null) 
		    {
		    	Matcher m1 = r.matcher(sCurrentLine);
		    	Matcher m2 = r2.matcher(sCurrentLine);
		    	if(m1.find())
		    	{
					
				   //System.out.println( m1.group(0));
				   int id = Integer.parseInt(m1.group(1));
				   int ts = Integer.parseInt(m1.group(2));
				 /* String[] s = m1.group(3).split(" ");
				  
				   ArrayList<Point> polyPoint = new ArrayList();
				   for(String substr:s)
				   {
					   String[] pstr = substr.split(",");
					// if(id==12 && ts==12) System.out.println(pstr[0]+" "+pstr[1]);
					   polyPoint.add(new Point(Double.parseDouble(pstr[0]),Double.parseDouble(pstr[1])));
				   }
				  */ 
				   StringTokenizer st = new StringTokenizer(m1.group(3)," ");
				   ArrayList<Point> polyPoint = new ArrayList();
				   while(st.hasMoreTokens())
				   {
					   StringTokenizer st2 = new StringTokenizer(st.nextToken(),",");
					// if(id==12 && ts==12) System.out.println(pstr[0]+" "+pstr[1]);
					   polyPoint.add(new Point(Double.parseDouble(st2.nextToken()),Double.parseDouble(st2.nextToken())));
				   }
				   
				   Point[] outArray = polyPoint.toArray(new Point[polyPoint.size()]); 
				 		 
				   if( m2.find()) 
				   {
					   /*
					   s = m2.group(1).split(" ");
					   ArrayList<Point> polyPoint2 = new ArrayList();
					   for(String substr:s)
					   {
						   String[] pstr = substr.split(",");
						  // System.out.println(pstr[0]+" "+pstr[1]);
						   polyPoint2.add(new Point(Double.parseDouble(pstr[0]),Double.parseDouble(pstr[1])));
					   }
					   */
					   st = new StringTokenizer(m2.group(1)," ");
					   ArrayList<Point> polyPoint2 = new ArrayList();
					   while(st.hasMoreTokens())
					   {
						   StringTokenizer st2 = new StringTokenizer(st.nextToken(),",");
						// if(id==12 && ts==12) System.out.println(pstr[0]+" "+pstr[1]);
						   polyPoint.add(new Point(Double.parseDouble(st2.nextToken()),Double.parseDouble(st2.nextToken())));
					   }
					   
					   Point[] inArray = polyPoint2.toArray(new Point[polyPoint2.size()]);
					   
					   if(outArray==null) System.out.println("out");
					   if(inArray==null) System.out.println("in");
					   //polyList.add(new Polygon(id,ts,inArray,outArray));
					   ModifyPolygon tempPoly = new ModifyPolygon();
					   for( Point p : outArray)
					   {
						   tempPoly.addPoint(p);
					   }
					   for( Point p : inArray)
					   {
						   tempPoly.addInnerPoint(p);
					   }
					   tempPoly.id = id;
					   tempPoly.ts = ts;
					   polyList.add(tempPoly);
					  				   
				   }
				   else
				   {
					   ModifyPolygon tempPoly = new ModifyPolygon();
					   for( Point p : outArray)
					   {
						   tempPoly.addPoint(p);
					   }
					   tempPoly.id = id;
					   tempPoly.ts = ts;
					   polyList.add(tempPoly);
						
				   }
				   // Update polygon ts hashtable
				   if(polyTsTable.containsKey(id))
				   {
					   ArrayList tempList =  polyTsTable.get(id);
					   tempList.add(ts);
					   polyTsTable.put(id, tempList ); 
				   }
				   else
				   {
					   ArrayList<Integer> tempList = new ArrayList();
					   tempList.add(ts);
					   polyTsTable.put(id, tempList ); 
				   }
			   
		    	}
				
			}
 
		 } catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				if (br != null)br.close();
			} catch (IOException ex) {
				ex.printStackTrace();
			}
		}
		

		
		
	}
	
	private void readPolyNIO(){
		polyList = new ArrayList();
		String pattern = "POLYGON:([0-9]*):([0-9]*).*<gml:outerBoundaryIs><gml:LinearRing><gml:coordinates decimal=\".\" cs=\",\" ts=\" \">(.*)</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs>";
		String pattern2 = "<gml:innerBoundaryIs><gml:LinearRing><gml:coordinates decimal=\".\" cs=\",\" ts=\" \">(.*)</gml:coordinates></gml:LinearRing></gml:innerBoundaryIs>";
		
		Pattern r = Pattern.compile(pattern);
		Pattern r2 = Pattern.compile(pattern2);
		try 
		{
 
			String sCurrentLine ="";
 
			RandomAccessFile f = new RandomAccessFile(inPolyFile, "r");
			MappedByteBuffer in = f.getChannel().map(FileChannel.MapMode.READ_ONLY, 0, f.length());
			//System.out.println(f.length());
			int size=0;
			long len = f.length();
			//Vector<Character> b = new Vector<Character>(); 
		//	ArrayList<Character> b = new ArrayList<Character>();
			StringBuilder sb = new StringBuilder();
			
		    while (size<len) 
		    {
		    	
		    	char newChar = (char)in.get(size);
		    	if(newChar != '\n'){
		    		sb.append(newChar);
		    		//System.out.print(newChar);
		    		
		    	}
		    	else{
		    		//
		    		
		    		sCurrentLine=sb.toString();		    		
			    	Matcher m1 = r.matcher(sCurrentLine);
			    	Matcher m2 = r2.matcher(sCurrentLine);
			    	if(m1.find())
			    	{
						
					   //System.out.println( m1.group(0));
					   int id = Integer.parseInt(m1.group(1));
					   int ts = Integer.parseInt(m1.group(2));
					  /* String[] s = m1.group(3).split(" ");
					   ArrayList<Point> polyPoint = new ArrayList();
					   for(String substr:s)
					   {
						   String[] pstr = substr.split(",");
						// if(id==12 && ts==12) System.out.println(pstr[0]+" "+pstr[1]);
						   polyPoint.add(new Point(Double.parseDouble(pstr[0]),Double.parseDouble(pstr[1])));
					   }
					   */
					   
					   StringTokenizer st = new StringTokenizer(m1.group(3)," ");
					   ArrayList<Point> polyPoint = new ArrayList();
					   while(st.hasMoreTokens())
					   {
						   StringTokenizer st2 = new StringTokenizer(st.nextToken(),",");
						// if(id==12 && ts==12) System.out.println(pstr[0]+" "+pstr[1]);
						   polyPoint.add(new Point(Double.parseDouble(st2.nextToken()),Double.parseDouble(st2.nextToken())));
					   }
					   Point[] outArray = polyPoint.toArray(new Point[polyPoint.size()]); 
					 		 
					   if( m2.find()) 
					   {
						  // s = m2.group(1).split(" ");
						  /* ArrayList<Point> polyPoint2 = new ArrayList();
						   for(String substr:s)
						   {
							   String[] pstr = substr.split(",");
							  // System.out.println(pstr[0]+" "+pstr[1]);
							   polyPoint2.add(new Point(Double.parseDouble(pstr[0]),Double.parseDouble(pstr[1])));
						   }
						   */
						   st = new StringTokenizer(m2.group(1)," ");
						   ArrayList<Point> polyPoint2 = new ArrayList();
						   while(st.hasMoreTokens())
						   {
							   StringTokenizer st2 = new StringTokenizer(st.nextToken(),",");
							// if(id==12 && ts==12) System.out.println(pstr[0]+" "+pstr[1]);
							   polyPoint.add(new Point(Double.parseDouble(st2.nextToken()),Double.parseDouble(st2.nextToken())));
						   }
						   
						   Point[] inArray = polyPoint2.toArray(new Point[polyPoint2.size()]);
						   
						   if(outArray==null) System.out.println("out");
						   if(inArray==null) System.out.println("in");
						   //polyList.add(new Polygon(id,ts,inArray,outArray));
						   ModifyPolygon tempPoly = new ModifyPolygon();
						   for( Point p : outArray)
						   {
							   tempPoly.addPoint(p);
						   }
						   for( Point p : inArray)
						   {
							   tempPoly.addInnerPoint(p);
						   }
						   tempPoly.id = id;
						   tempPoly.ts = ts;
						   polyList.add(tempPoly);
						  				   
					   }
					   else
					   {
						   ModifyPolygon tempPoly = new ModifyPolygon();
						   for( Point p : outArray)
						   {
							   tempPoly.addPoint(p);
						   }
						   tempPoly.id = id;
						   tempPoly.ts = ts;
						   polyList.add(tempPoly);
							
					   }
					   // Update polygon ts hashtable
					   if(polyTsTable.containsKey(id))
					   {
						   ArrayList tempList =  polyTsTable.get(id);
						   tempList.add(ts);
						   polyTsTable.put(id, tempList ); 
					   }
					   else
					   {
						   ArrayList<Integer> tempList = new ArrayList();
						   tempList.add(ts);
						   polyTsTable.put(id, tempList ); 
					   }
				   
			    	}
			    	//sCurrentLine="";
			    	sb = new StringBuilder();
		    	}
				size++;
			}
 
		 } catch (Exception e) {
			 System.out.println(e);
			e.printStackTrace();
		} finally {
			
		}
	}
	
	private int checkSequence(int pointTs , int polyId){
		ArrayList myList = polyTsTable.get(polyId);
		int maxPolyTs = (Integer)myList.get(0);
		for(int i = 1 ; i<myList.size();i++){
			int currTs;
			if((currTs=(Integer)myList.get(i))<pointTs && currTs>maxPolyTs) maxPolyTs = currTs; 
		}
		return maxPolyTs;
	}
	
	private void checkInside(){
		resultList  = new ArrayList();
		int i=0;
		while(i<pointList.size()){
			Point tempPoint = pointList.get(i);
			int j = 0;
			while( j < polyList.size()){
				ModifyPolygon tempPoly = polyList.get(j);
				if(tempPoly.ts == checkSequence(tempPoint.timestamp , tempPoly.id)){
					if(tempPoly.contains(tempPoint)){
						//System.out.println(tempPoint.id+":"+tempPoint.timestamp+":"+tempPoly.getid()+":"+tempPoly.gettimestamp());
						resultList.add(new ResultClass(tempPoint.id,tempPoint.timestamp,tempPoly.id,tempPoly.ts));
					}
				}
				j++;
			}
			i++;
		}
	}
	
	private void checkInside(int nThreads){
		resultList  = new ArrayList();
		Thread[] mythread = new InsideThread[nThreads];
		for(int i = 0; i<nThreads;i++){
			mythread[i] = new InsideThread(i,nThreads);
			mythread[i].start();
		}
		try{
			for(Thread m : mythread){
				m.join();
			}
		}catch(Exception e){
			
		}
		
	}
	
	private void checkWithin(int nThreads){
		resultList  = new ArrayList();
		Thread[] mythread = new WithinThread[nThreads];
		for(int i = 0; i<nThreads;i++){
			mythread[i] = new WithinThread(i,nThreads);
			mythread[i].start();
		}
		try{
			for(Thread m : mythread){
				m.join();
			}
		}catch(Exception e){
			
		}
	}
	
	private void checkWithin(){
		resultList  = new ArrayList();
		int i=0;
		while(i<pointList.size()){
			Point tempPoint = pointList.get(i);
			int j = 0;
			while( j < polyList.size()){
				ModifyPolygon tempPoly = polyList.get(j);
				if(tempPoly.ts == checkSequence(tempPoint.timestamp , tempPoly.id)){
					if(tempPoly.within(tempPoint,withinDist)){
						//System.out.println(tempPoint.id+":"+tempPoint.timestamp+":"+tempPoly.getid()+":"+tempPoly.gettimestamp());
						resultList.add(new ResultClass(tempPoint.id,tempPoint.timestamp,tempPoly.id,tempPoly.ts));
					}
				}
				j++;
			}
			i++;
		}
	}
	
	class InsideThread extends Thread {
		  private int index;
		  private int n;
		  InsideThread(int index,int n) {
		    this.index = index;
		    this.n = n;
		  }

		  @Override
		  public void run() {
			  if( index < n-1){
				  for(int i = (index*pointList.size())/n ; i<((index+1)*pointList.size())/n-1;i++){
						Point tempPoint = pointList.get(i);
						int j = 0;
						while( j < polyList.size()){
							ModifyPolygon tempPoly = polyList.get(j);
							if(tempPoly.ts == checkSequence(tempPoint.timestamp , tempPoly.id)){
								if(tempPoly.contains(tempPoint)){
									//System.out.println(tempPoint.id+":"+tempPoint.timestamp+":"+tempPoly.getid()+":"+tempPoly.gettimestamp());
									synchronized (resultList) {
								          // mutual exclusive section
										resultList.add(new ResultClass(tempPoint.id,tempPoint.timestamp,tempPoly.id,tempPoly.ts));
								     }
								}
							}
							j++;
						}
						
					}
			  }
			  else{
				  for(int i = (index*pointList.size())/n ; i<pointList.size();i++){
						Point tempPoint = pointList.get(i);
						int j = 0;
						while( j < polyList.size()){
							ModifyPolygon tempPoly = polyList.get(j);
							if(tempPoly.ts == checkSequence(tempPoint.timestamp , tempPoly.id)){
								if(tempPoly.contains(tempPoint)){
									//System.out.println(tempPoint.id+":"+tempPoint.timestamp+":"+tempPoly.getid()+":"+tempPoly.gettimestamp());
									synchronized (resultList) {
										resultList.add(new ResultClass(tempPoint.id,tempPoint.timestamp,tempPoly.id,tempPoly.ts));
									}
								}
							}
							j++;
						}						
					}
			  }
		  }
		} 
	
	class WithinThread extends Thread {
		  private int index;
		  private int n;
		  WithinThread(int index,int n) {
		    this.index = index;
		    this.n = n;
		  }

		  @Override
		  public void run() {
			  if( index < n-1){
				  for(int i = (index*pointList.size())/n ; i<((index+1)*pointList.size())/n-1;i++){
						Point tempPoint = pointList.get(i);
						int j = 0;
						while( j < polyList.size()){
							ModifyPolygon tempPoly = polyList.get(j);
							if(tempPoly.ts == checkSequence(tempPoint.timestamp , tempPoly.id)){
								if(tempPoly.within(tempPoint,withinDist)){
									//System.out.println(tempPoint.id+":"+tempPoint.timestamp+":"+tempPoly.getid()+":"+tempPoly.gettimestamp());
									synchronized (resultList) {
										resultList.add(new ResultClass(tempPoint.id,tempPoint.timestamp,tempPoly.id,tempPoly.ts));
									}
								}
							}
							j++;
						}
						
					}
			  }
			  else{
				  for(int i = (index*pointList.size())/n ; i<pointList.size();i++){
						Point tempPoint = pointList.get(i);
						int j = 0;
						while( j < polyList.size()){
							ModifyPolygon tempPoly = polyList.get(j);
							if(tempPoly.ts == checkSequence(tempPoint.timestamp , tempPoly.id)){
								if(tempPoly.within(tempPoint,withinDist)){
									//System.out.println(tempPoint.id+":"+tempPoint.timestamp+":"+tempPoly.getid()+":"+tempPoly.gettimestamp());
									synchronized (resultList) {
										resultList.add(new ResultClass(tempPoint.id,tempPoint.timestamp,tempPoly.id,tempPoly.ts));
									}
								}
							}
							j++;
						}						
					}
			  }
		  }
		} 

	private void printResult(){
		Collections.sort(resultList);
		int i=0;
		while(i<resultList.size()){
			System.out.println(resultList.get(i).getResult());
			i++;
		}
	}
	
	private String padRight(String s, int n) {
	     return String.format("%1$-" + n + "s", s);  
	}
	
	private void outputResult(){
		
		Collections.sort(resultList);
		int i=0;
		try { 
			File file = new File(outFile);
 
			// if file doesnt exists, then create it
			if (!file.exists()) {
				file.createNewFile();
			}
 
			FileWriter fw = new FileWriter(file.getAbsoluteFile());
			BufferedWriter bw = new BufferedWriter(fw);
			while(i<resultList.size()){
				bw.write(padRight(resultList.get(i).getResult(),80)+"\n");
				i++;
			}
			
			bw.close();
 
			//System.out.println("Done");
 
		} catch (IOException e) {
			e.printStackTrace();
		}


	}
	
	private void outputResultNIO(){
		Collections.sort(resultList);
		
		outputSize=0;
		int resultListSize = resultList.size();
		for(int m = 0 ; m < resultListSize;m++ ){
			//outputSize+= resultList.get(m).getResult().length();
		}
		
		int i=0;
		try { 
			//FileChannel fc = new RandomAccessFile(outFile, "rw").getChannel();
			RandomAccessFile fc = new RandomAccessFile(outFile, "rw");
			  MappedByteBuffer out = fc.getChannel().map(FileChannel.MapMode.READ_WRITE, 0, resultList.size()*81);
			//CharBuffer cb = fc.map(FileChannel.MapMode.READ_WRITE, 0,resultList.size()*200).asCharBuffer();
			while(i<resultList.size()){
				String str = padRight(resultList.get(i).getResult(),80)+"\n";
				
				//String str = resultList.get(i).getResult()+"\n";
				byte[] c = str.getBytes();
				//System.out.println(c.length);
				out.put(c);
				//cb.put(c);
				i++;
			} 
			fc.close();
			//System.out.println("Done");
 
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	public static void main(String[] args){
		long startTime = System.currentTimeMillis();
		new GeoFence("./TrainingDataSet/points1000.txt","./TrainingDataSet/poly15.txt","./Result/r3.txt");		
		  long stopTime = System.currentTimeMillis();
		  long elapsedTime = stopTime - startTime;
		  System.out.println("Total:"+elapsedTime);
	      Runtime runtime = Runtime.getRuntime();
	      // Run the garbage collector
	      runtime.gc();
	      // Calculate the used memory
	      long memory = runtime.totalMemory() - runtime.freeMemory();
	      System.out.println("Used memory is: " + memory/1024 + " 	MB");
	}
}
